/**
 * \file ArbreCousu.h
 * \brief Classe d�finissant un arbre cousu
 * \author Abder
 * \version 0.1
 * \date mai 2011
 */

#ifndef _AC
#define _AC

//#pragma warning( disable : 4290 )
#include <stdexcept>
#include <iostream>

/** 
* \class ArbreCousu
*
* \brief classe g�n�rique repr�sentant un arbre cousu
*
*  La classe g�re un arbre g�n�rique. 
*  L'impl�mentation se fait par cha�nage.
*/ 
template <typename E>
class ArbreCousu
{
public:
	/**
     *  \brief Constructeur  
	 *
	 * \post Une instance de la classe ArbreCousu est initialis�e
     */
	ArbreCousu();

	/**
     *  \brief Constructeur de copie
	 *
	 * \pre Il faut qu'il y ait suffisamment de m�moire
	 *  \post une copie profonde de l'arbre source est instanci�e
	 *  \exception bad_alloc s'il n'y a pas assez de m�moire
     */
	ArbreCousu(const ArbreCousu& source) throw(std::bad_alloc);

	/**
     *  \brief Destructeur
     *
     *  \post l'instance de l'arbre est d�truite
     */
	~ArbreCousu();

	/**                       
	 *  \brief Ins�rer un �l�ment dans l'arbre
	 *
	 * Insertion dans l'ordre de tri et sans balancement
	 *
	 * \pre Il y a assez de m�moire
	 * \post L'arbre contient un �l�ment de plus
	 * \exception bad_alloc s'il n'y a pas assez de m�moire
	 */
	void inserer(const E &data) throw(std::bad_alloc);

	/**                       
	 *  \brief Couture de l'arbre binaire
	 *
	 * Couture de l'arbre suivant la visite sym�trique
	 * dans les 2 sens: de successeur � successeur et de
	 * pr�d�cesseur � pr�d�cesseur (couture dans les 2 sens)
	 *
	 * \post L'arbre courant est cousu
	 */
	void couture() const;

	/**                       
	 *  \brief Affiche l'arbre en ordre croissant
	 *
	 *  L'affichage se fait apr�s la couture
	 *  La m�thode utilise une fonction auxiliaire
	 *
	 * \post L'arbre est inchang�
	 * \post L'arbre est affich� en ordre croissant
	 */
	void afficherCr() const;

	/**                       
	 *  \brief Affiche l'arbre en ordre D�croissant
	 *
	 *  L'affichage se fait apr�s la couture
	 *  La m�thode utilise une fonction auxiliaire
	 *
	 * \post L'arbre est inchang�
	 * \post L'arbre est affich� en ordre d�croissant
	 */
	void afficherDe() const;

	//surcharge d'op�rateurs
	/**                       
	 * \brief Surcharger l'op�rateur = 
	 *
	 * \pre Il y a assez de m�moire pour l'op�ration 
	 * \post Une copie d'un arbre est retourn�e
	 * \exception bad_alloc si la m�moire est insuffisante
	 */
	const ArbreCousu<E>& operator = (const ArbreCousu & a) throw(std::bad_alloc);  


private:
	/** 
	* \class Noeud
	*
	* \brief classe interne repr�sentant un noeud typique de l'arbre
	*
	*  La classe repr�sente un noeud typique
	*  pour impl�menter un arbre par cha�nage.
	*/
	class Noeud
	{
	  public:
		E data;			/*!< La donn�e dans l'arbre*/
		Noeud *gauche;	/*!< Pointeur vers le fils gauche*/
		Noeud *droite;	/*!< Pointeur vers le fils droit*/
		bool filGauche; /*!< indique si gauche est un fil ou non */
		bool filDroit; /*!< indique si droite est un fil ou non */
		/**                       
		 * \brief Constructeur de la classe Noeud
		 *
		 * \post un noeud typique est intialis�
		 * 
		 */
		Noeud( const E&d ): data( d ), gauche( 0 ), droite( 0 ), filGauche(false), filDroit(false){ }
	};

	// Les membres donn�es
	Noeud * racine;	/*!< La racine de l'arbre*/
	long int cpt; /*!< La cardinalit� de l'arbre*/
	
	// Les membres fonctions priv�s
	// Des auxiliaires r�cursifs
	
	/**                       
	 *  \brief Coudre un arbre de tri
	 *
	 *  Fonction auxiliaire (r�cursive)
	 * \post L'arbre est cousu
	 */
	Noeud * _laCouture(Noeud * racine) const;

	/**                       
	 *  \brief Retourner le successeur d'un �l�ment dans un sous-arbre
	 *
	 *  Fonction auxiliaire (r�cursive)
	 *
	 * \pre Le sous-arbre n'est pas vide
	 * \pre L'�l�ment fait partie du sous-arbre
	 * \pre L'�l�ment n'est pas le maximum dans le sous-arbre
	 * \post Le sous-arbre est inchang�
	 * \exception logic_error si le sous-arbre est vide 
	 * \exception logic_error si l'�l�ment n'est pas dans le sous-arbre
	 * \exception logic_error si l'�l�ment est le maximum dans le sous-arbre
	 */
	E  _successeur(Noeud*, const E&) const throw(std::logic_error);

	/**                       
	 *  \brief Retourner le pr�d�cesseur d'un �l�ment dans un sous-arbre
	 *
	 *  Fonction auxiliaire (r�cursive)
	 *
	 * \pre Le sous-arbre n'est pas vide
	 * \pre L'�l�ment fait partie du sous-arbre
	 * \pre L'�l�ment n'est pas le minimum dans le sous-arbre
	 * \post Le sous-arbre est inchang�
	 * \exception logic_error si le sous-arbre est vide 
	 * \exception logic_error si l'�l�ment n'est pas dans le sous-arbre
	 * \exception logic_error si l'�l�ment est le minimum dans le sous-arbre
	 */
	E  _predecesseur(Noeud*, const E&) const throw(std::logic_error);

	/**                       
	 *  \brief Retourner le parent d'un �l�ment dans sous-arbre
	 *
	 * Fonction auxiliaire (r�cursive)
	 *
	 * \pre Le sous-arbre n'est pas vide
	 * \pre L'�l�ment fait partie du sous-arbre
	 * \post L'arbre est inchang�
	 * \exception logic_error si le sous-arbre est vide 
	 * \exception logic_error si l'�l�ment n'est pas dans le sous-arbre
	 */
	Noeud* _parent(Noeud*, Noeud*) const throw (std::logic_error);

	/**                       
	 *  \brief Chercher un �l�ment dans un sous-arbre
	 *
	 * Fonction auxiliaire (r�cursive). 
	 *
	 * \post Le sous-arbre est inchang�
	 */
	Noeud* _auxAppartient(Noeud* arbre, const E &data) const;

	/**                       
	 *  \brief Retourner la valeur maximum dans un sous-arbre
	 *
	 * Fonction auxiliaire (r�cursive)
	 *
	 * \pre Le sous-arbre n'est pas vide
	 * \post Le sous-arbre est inchang�
	 * \exception logic_error si le sous-arbre est vide
	 */
	const E& _max(Noeud*)const throw (std::logic_error);

	/**                       
	 *  \brief Retourner la valeur minimum dans un sous-arbre
	 *
	 * Fonction auxiliaire (r�cursive)
	 *
	 * \pre Le sous-arbre n'est pas vide
	 * \post Le sous-arbre est inchang�
	 * \exception logic_error si le sous-arbre est vide
	 */
	const E& _min(Noeud*)const throw (std::logic_error);

	/**                       
	 *  \brief Copier deux sous-arbre
	 *
	 * Fonction auxiliaire. Cas d'un tableau en argument.
	 *
	 * \post Le sous-arbre source est inchang� 
	 */
	void _auxCopier( Noeud *, Noeud*&) throw (std::bad_alloc);

	/**                       
	 *  \brief D�truire un sous-arbre
	 *
	 * \post Le sous-arbre est d�truit
	 */
	void  _auxDetruire(Noeud *&);

	/**                       
	 *  \brief Ins�rer �l�ment dans un sous-arbre
	 *
	 * Fonction auxiliaire (r�cursive). Insertion sans balancement
	 *
	 * \post Le sous-arbre contient un �l�ment de plus 
	 */
	void _auxInserer( Noeud *&, const E&);

	/**                       
	 *  \brief Afficher l'arbre en ordre croissant
	 *
	 * Fonction auxiliaire (r�cursive).  
	 */
	void _afficheArbDe (Noeud * racine) const;

	/**                       
	 *  \brief Afficher l'arbre en ordre croissant
	 *
	 * Fonction auxiliaire (r�cursive).  
	 */
	void _afficheArbCr (Noeud * racine)const ;
};

#include "ArbreCousu.hpp"

#endif






